<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<html><head>
<!--Converted with LaTeX2HTML 98.1 release (February 19th, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
  Jens Lippmann, Marek Rouchal, Martin Wilck and others -->


<title>The Collatz Sequence</title>
<meta name="description" content="The Collatz Sequence">
<meta name="keywords" content="htmlatex">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<link rel="STYLESHEET" href="acm-00694_files/htmlatex.css">
</head><body bgcolor="#ffffff" lang="EN">

<h1><br clear="all"><center><table bgcolor="#0060f0"><tbody><tr><td><b><font color="#c0ffff" size="5">&nbsp;<a name="SECTION0001000000000000000000">
The Collatz Sequence</a>&nbsp;</font></b></td></tr></tbody></table></center>
</h1>

<p>
An algorithm given by Lothar Collatz produces sequences of integers, and is
described as follows:
</p><dl>
<dt><strong>Step 1:</strong>
</dt><dd>Choose an arbitrary positive integer <i>A</i> as the first item in
the sequence.
</dd><dt><strong>Step 2:</strong>
</dt><dd>If <i>A</i> = 1 then stop.
</dd><dt><strong>Step 3:</strong>
</dt><dd>If <i>A</i> is even, then replace <i>A</i> by <i>A</i> / 2 and go to step 2.
</dd><dt><strong>Step 4:</strong>
</dt><dd>If <i>A</i> is odd, then replace <i>A</i> by 3 * <i>A</i> + 1 and go to step 2.
</dd></dl>

<p>
It has been shown that this algorithm will always stop (in step 2) for initial
values of <i>A</i> as large as 10<sup>9</sup>, but some values of <i>A</i> encountered in
the sequence may exceed the size of an integer on many computers.  In this
problem we want to determine the length of the sequence that includes all
values produced until either the algorithm stops (in step 2), or a value
larger than some specified limit would be produced (in step 4).

</p><p>

</p><h2><font color="#0070e8"><a name="SECTION0001001000000000000000">
Input</a>&nbsp;</font>
</h2>
The input for this problem consists of multiple test cases.  For each case,
the input contains a single line with two positive integers, the first giving
the initial value of <i>A</i> (for step 1) and the second giving <i>L</i>, the limiting
value for terms in the sequence.  Neither of these, <i>A</i> or <i>L</i>, is larger
than 2,147,483,647 (the largest value that can be stored in a 32-bit signed
integer).  The initial value of <i>A</i> is always less than <i>L</i>.  A line that
contains two negative integers follows the last case.

<p>

</p><h2><font color="#0070e8"><a name="SECTION0001002000000000000000">
Output</a>&nbsp;</font>
</h2>
For each input case display the case number (sequentially numbered starting
with 1), a colon, the initial value for <i>A</i>, the limiting value <i>L</i>, and the
number of terms computed.

<p>

</p><h2><font color="#0070e8"><a name="SECTION0001003000000000000000">
Sample Input</a>&nbsp;</font>
</h2>

<p>
</p><pre> 3 100
 34 100
 75 250
 27 2147483647
 101 304
 101 303
 -1 -1
</pre>

<p>

</p><h2><font color="#0070e8"><a name="SECTION0001004000000000000000">
Sample Output</a>&nbsp;</font>
</h2>
				
<pre> Case 1: A = 3, limit = 100, number of terms = 8
 Case 2: A = 34, limit = 100, number of terms = 14
 Case 3: A = 75, limit = 250, number of terms = 3
 Case 4: A = 27, limit = 2147483647, number of terms = 112
 Case 5: A = 101, limit = 304, number of terms = 26
 Case 6: A = 101, limit = 303, number of terms = 1
</pre>

<p>

</p><p>
<br></p><hr>
<address>
<i>Miguel Revilla</i>
<br><i>2000-08-14</i>
</address>
</body></html>